import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;

/**
 * 输入n个整数,找出其中最小的k个数
 * 例如:输入4,5,1,6,2,7,3,8  则最小的4个数字是1,2,3,4
 * 解题思路:
 * 1.直接升序排序,取前n个,
 * 2.可以采用最大堆,PriorityQueue优先级队列
 * 最大堆(大根堆):树中每个非叶子节点大于其左右孩子结点的值,也就是根节点最大的堆
 * 最小堆(小根堆):树中每个非叶子节点都不大于其左右孩子节点的值,也就是根节点最小的堆
 *
 */
public class topK {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if (input == null || k <= 0 || input.length < k) {
            return list;
        }
        //按照数值从大到小
        PriorityQueue<Integer> queue = new PriorityQueue<>(k, Collections.reverseOrder());
        for (int i = 0; i < input.length; i++) {
            if (i < k) {
                //先给堆中放入k个元素
                queue.offer(input[i]);
            }else {
                //开始淘汰,每次淘汰最大的
                if (input[i] < queue.peek()) {
                    queue.poll();//将最大值弹出
                    queue.offer(input[i]);//再将i入堆
                }
            }
        }
        for (int i = 0; i < k; i++) {
            list.add(queue.poll());
        }
        return list;
    }
}
